Понятия со словосочетанием «машина Тьюринга»

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Вероятностная машина Тьюринга представляет собой детерминированную машину Тьюринга, имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту и потом использовать в вычислениях обычным для МТ образом.

Недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.

Квантовая машина Тьюринга (англ. Quantum Turing machine; иногда — универсальный квантовый компьютер) — абстрактная машина, используемая для моделирования квантового компьютера. Представляет собой простую модель, которая, в то же время, может описать любые квантовые вычисления. Любой квантовый алгоритм может быть формально описан как некоторая квантовая машина Тьюринга. Впервые подобные модели были предложены в 1985 году в работе Дэвида Дойча (Oxford University)В настоящее время КМТ используются не...